1. Field of the Invention
The present invention relates to an error correcting method and apparatus for correcting errors that arise in digital equipment or digital communications.
2. Description of the Prior Art
To correct errors that occur in digital equipment using a compact disk (CD), a digital audio tape (DAT), or the like or in digital communications, error correcting methods are selectively used according to the number of errors in the signal to be decoded. In such error correcting methods a Reed-Solomon code (hereinafter referred to as an "RS code") has been in wide use as an error correcting code for correcting errors in one signal on a byte-by-byte basis.
As decoding methods for the RS code, there are known a Peterson's algorithm, a Berlekamp's algorithm, a Euclid's algorithm and so forth, but when the error correcting power is small (single or double), the Peterson's algorithm is usually employed because of ease in calculation.
Roughly speaking, the decoding process by the Peterson's algorithm comprises the four steps mentioned below.
1. To calculate syndromes from the received word;
2. To estimate the number of errors and formulate an error position equation;
3. To find out the root of the error position equation; and
4. Calculate the value of error at each position corresponding to the root.
Of the above four steps, step 3 is usually performed using a Chien Search method that successively searches for the root while substituting elements of the Galois field into the error position equation.
As an example of such a Peterson's algorithm, there is disclosed, for example, in Japanese Pat. Pub. Gazette No. 7848/92, the following algorithm that follows the above procedure.
In the first place, syndromes S0, S1, S2 and S3 are calculated from the received word and operation expressions A, B and C are solved as follows: EQU A=S0S2+S1.sup.2 EQU B=S1S2+S0S3 EQU C=S1S3+S2.sup.2
The number of errors (the error count) is estimated from the above and the necessary correction is made as follows;
(1) When A=B=C=0 and S0=S3=0, it is estimated that there is no error.
(2) When A=B=C=0 and S0.noteq.0 and S3.noteq.0, it is estimated that a single error has arisen. At this time, an error position i and an error value e bear the following relationship: EQU .alpha..sup.i =S1/S0 e=S0
where .alpha. is a root of an irreducible polynomial F(x). The error position can be determined by prestoring a table of correspondence between the error position i and the root .alpha..sup.i in a ROM and retrieving it with the value S1/S0. The error value is S0.
(3) When A.noteq.0 and B.noteq.0 and C.noteq.0, it is estimated that a double error has occurred. At this time, the error equation is such as follows: EQU Ax.sup.2 +Bx+C=0
Letting the two roots be represented by .alpha..sup.i and .alpha..sup.j (where 0.ltoreq.i&lt;j.ltoreq.n-1), respectively, EQU .alpha..sup.i +.alpha..sup.j =D EQU .alpha..sup.i .alpha..sup.j =E
where D=B/A and E=C/A.
Letting the difference between the two error positions, that is, the difference between the two roots .alpha..sup.i and .alpha..sup.j, be represented by t (where t=j-i), the following modifications can be made: EQU D=.alpha..sup.i (1+.alpha..sup.t) EQU E=.alpha..sup.2i+t
Therefore, EQU D.sup.2 /E=.alpha..sup.t +.alpha..sup.-t
can be obtained. The difference t can be obtained by prestoring a table of values .alpha..sup.t +.alpha..sup.-t corresponding to t(where 1.ltoreq.t.ltoreq.n-1) in the ROM and retrieving it with the value D.sup.2 /E.
By calculating EQU X=1+.alpha..sup.t EQU Y=1+.alpha..sup.-t =D.sup.2 /E+X
from the above, the two roots can be obtained as follows: EQU .alpha..sup.i =D/X EQU .alpha..sup.j =D/Y
Thus the error positions i and j can be obtained by retrieving the table in the ROM with the values D/X and D/Y as is the case with the single error. And error values e.sub.i and e.sub.j at the error positions i and j are calculated as follows: EQU e.sub.i =(.alpha..sup.j S0+S1)/D EQU e.sub.j =(.alpha..sup.i S0+S1)/D
Since the conventional error correcting method is such as described above, the calculation of the syndrome values from received words is immediately followed by the calculation of the operation expressions A, B and C. However, for some of the received words it is impossible to perform error correction and the calculation of the operation expressions A, B and C for such received word is entirely useless processing--this gives arise to a problem that much time may sometimes be consumed to decide that for the received words it is impossible to perform error correction.
Based on the values of the syndromes S0, S1, S2 and S3 and the operation expressions A, B and C, the decision is made as to whether to make the error correction and no error pattern impossible of error correction can be detected from the values of the syndromes S0, S1, S2 and S3 alone; hence, a complex operation is needed to decide whether or not the error correction is to be made.
Another problem is that the condition for detecting the double error is complex because it is detected based on the values of the three operation expressions A, B and C.
Furthermore, the error correction begins with calculating the element .alpha..sup.i of the Galois field corresponding to the error position, followed by determination of the error position i by retrieving the table stored in the ROM. Accordingly, the decoding delay increases and the circuit scale is also large because of the use of the ROM.
Additionally, according to the conventional error correcting method, division needs to be done seven times for making a double error correction, but the computational load of division is so large that the decoding delay is significantly affected.